Finding minimal vertex extensions of a colored undirected graph 

Mikhail B. Abrosimov, Doctor of physical and mathematical sciences, associate professor, head of the sub-department of computer security theory and cryptography, Saratov State University (83 Astrakhanskaya street, Saratov, Russia), mic@rambler.ru
Petr V. Razumovskiy, Postgraduate student, Saratov State University (83 Astrakhanskaya street, Saratov, Russia), shprotby@gmail.com

519.17 

10.21685/2072-3040-2021-4-8 

Background. The research considers the results of the finding minimal vertex extensions of the colored undirected graphs. This topic relates to the modelling of the completely fault tolerant technical systems with the different typed objects in the terms of graph theory. The system could be described as some graph where vertices reflect system’s objects and edges are connection lines between these objects. Fault tolerance property is one of the technical system’s main properties, especially if such system works in the critical life areas: medicine, space, communication. Materials and methods. The article uses mathematical modelling methods of the technical systems in the terms of graph theory. The main research is focused on constructing non-isomorphic fault tolerant implementations of the colored undirected graphs. The constructing algorithms uses isomorphic rejection and canonical labelling techniques. Results. The article considers the problem of the search for minimal vertex k-extensions of the colored graphs without isomorphism verification. The study proposes the algorithm of finding all non-isomorphic minimal vertex k-extensions for the defined colored graph. Conclusions. The proposed algorithm was implemented as a runnable executable program. There are some experiment calculations for the various configurations of the colored graphs. 

graph extensions, graph coloring, colored graphs, minimal vertex extensions,  graph isomorphism, colored graph isomorphism 

1. Bogomolov A.M., Saliĭ V.N. Algebraicheskie osnovy teorii diskretnykh system = Algebraic foundations of the theory of discrete systems. Moscow: Nauka, 1997:368.
(In Russ.)
2. Hayes J.P. A graph model for fault-tolerant computing system. IEEE Trans. Comput. 1976;C.-25(9):875–884.
3. Abrosimov M.B. Grafovye modeli otkazoustoychivosti = Fault tolerance graph models. Saratov: Izd-vo Sarat. un-ta, 2012:192. (In Russ.)
4. McKay B.D., Piperno A. Practical Graph Isomorphism. J. Symbolic Computation. 2013;2(60):94–112.
5. Zykov A.A. Osnovy teorii grafov = Fundamentals of graph theory. Moscow: Vuzovskaya kniga, 2004:664. (In Russ.)
6. Kharari F. Teoriya grafov = The graph theory. Moscow: Mir, 1973:300. (In Russ.)
7. Brinkmann G. Isomorphism rejection in structure generation programs. Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000;51:25–38.
8. Abrosimov M.B., Kamil I.A.K., Lobov A.A. Construction of all minimal nonisomorphic minimal vertex extensions of a graph by the method of canonical representatives.
Izvestiya Saratovskogo universiteta. Novaya seriya. Ser. Matematika. Mekhanika. Informatika = Proceedings of Saratov University. New series. Series Mathematics. Mechanics. Informatics. 2019;19(4):479–486. (In Russ.)
9. Abrosimov M.B., Sudani Kh.Kh.K., Lobov A.A. Constructing minimal edge extensions of a graph without checking for isomorphism. Izvestiya Saratovskogo universiteta. Novaya seriya. Ser. Matematika. Mekhanika. Informatika = Proceedings of Saratov University. New series. Series Mathematics. Mechanics. Informatics. 2020;20(1):105–115. (In Russ.)